import ctypes


class DynamicArray:
    """
    A dynamic array class to a simplified Python list
    """
    def __init__(self):
        """
        Create an empty array
        """
        self._n = 0         # 当前长度
        self._capacity = 4  # 容量
        self._data = self._make_array(self._capacity)

    def __len__(self):
        """
        The number of elements stored in the array
        :return:
        """
        return self._n

    @property
    def capacity(self):
        return self._capacity

    def __getitem__(self, index):
        """
        Return element at index item.
        :param item:
        :return:
        """
        if index < 0:
            index += self._n
        if not 0 <= index < self._n:
            raise IndexError("Invalid index")
        return self._data[index]

    def __str__(self):
        t = []
        for i in range(self._n):
            t.append(self._data[i])
        return str(t)

    def _make_array(self, c):
        return (c * ctypes.py_object)()

    def _resize(self, c):
        """Resize array to capacity c."""
        temp = self._make_array(c)
        for i in range(self._n):
            temp[i] = self._data[i]
        self._data = temp
        self._capacity = c

    def count(self, value):
        """
        Return number of occurrences of value.
        :param value:
        :return:
        """
        cnt = 0
        for i in range(self._n):
            if value == self._data[i]:
                cnt += 1
        return cnt

    def clear(self):
        """
        Remove all items from list.
        :return:
        """
        for i in range(self._n):
            self._data[i] == None
        self._n = 0
        self._capacity = 1
        self._data = self._make_array(self._capacity)

    def append(self, obj):
        """
        append object to end of the array.
        :param obj:
        :return:
        """
        if self._n == self._capacity:
            self._resize(2 * self._capacity)
        self._data[self._n] = obj
        self._n += 1

    def insert(self, index, value):
        """
        Insert object before index
        :param index:
        :param object:
        :return:
        """
        if not 0 <= index <= self._n:
            raise IndexError("Invalid index")
        if self._n == self._capacity:
            # 扩展2倍
            temp = self._make_array(2 * self._capacity)
            #将原本data copy 到temp
            for i in range(index):
                temp[i] = self._data[i]
            #插入
            temp[index] = value
            #往后移动
            for j in range(index, self._capacity):
                temp[j+1] = self._data[j]
            self._data = temp
            self._capacity = 2 * self._capacity
        else:
            for i in range(self._n, index, -1):
                self._data[i] = self._data[i-1]
            self._data[index] = value
        self._n += 1

    def pop(self, index=-1):
        """
        Remove and return item at index(default last).
        Raises IndexError if list is empty or index is out of the range.
        :param index:
        :return:
        """
        if index < 0:
            index += self._n

        if not 0 <= index < self._n:
            raise IndexError("Invalid index")

        if index == self._n - 1:
            self._data[index] = None
            if self._n < self._capacity//4:
                temp = self._make_array(self._capacity // 2)
                for i in range(self._n):
                    temp[i] = self._data[i]
                self._data = temp
                self._capacity = self._capacity // 2
        else:
            for i in range(index, self._n - 1):
                self._data[i] = self._data[i+1]
            self._data[i+1] = None
        self._n -= 1

    def remove(self, value):
        """
        Remove first occurrence of value.
        Raises ValueError if the value is not present.
        :param value:
        :return:
        """
        for i in range(self._n):
            if self._data[i] == value:
                for j in range(i, self._n - 1):
                    self._data[j] = self._data[j+1]
                self._data[self._n - 1] = None
                self._n -= 1
                return
        raise ValueError("Value not found")

    def remove_all(self, value):
        """
        Remove all occurrence of value.
        Raises ValueError if the value is not present.
        O(n)
        :param value:
        :return:
        """
        keep = 0
        # 移动所有非value元素到list前面
        for i in range(self._n):
            if self._data[i] != value:
                self._data[keep] = self._data[i]
                keep += 1

        #删除剩下的元素
        while self._n > keep:
            self.pop()

    def index(self, value, start=0, stop=9223372036854775807):
        """
        Return first index of the value.
        Raises ValueError if the value is not present.
        :param value:
        :param start:
        :param stop:
        :return:
        """
        for i in range(self._n):
            if value == self._data[i]:
                return
        raise ValueError("Value not found")

